{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #删除链表的节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: deleteNode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除链表的节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。</p>\n",
    "\n",
    "<p>返回删除后的链表的头节点。</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> head = [4,5,1,9], val = 5\n",
    "<strong>输出:</strong> [4,1,9]\n",
    "<strong>解释: </strong>给定你链表中值为&nbsp;5&nbsp;的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -&gt; 1 -&gt; 9.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> head = [4,5,1,9], val = 1\n",
    "<strong>输出:</strong> [4,5,9]\n",
    "<strong>解释: </strong>给定你链表中值为&nbsp;1&nbsp;的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -&gt; 5 -&gt; 9.\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>说明：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>题目保证链表中节点的值互不相同</li>\n",
    "\t<li>若使用 C 或 C++ 语言，你不需要 <code>free</code> 或 <code>delete</code> 被删除的节点</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shan-chu-lian-biao-de-jie-dian-lcof](https://leetcode.cn/problems/shan-chu-lian-biao-de-jie-dian-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shan-chu-lian-biao-de-jie-dian-lcof](https://leetcode.cn/problems/shan-chu-lian-biao-de-jie-dian-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        # dummy\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        pre = dummy\n",
    "        while head:\n",
    "            if head.val == val:\n",
    "                pre.next = head.next\n",
    "                head.next = None\n",
    "            pre = head\n",
    "            head = head.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head is None:\n",
    "            return None\n",
    "        def func(node,val):\n",
    "            if node is None:\n",
    "                return None\n",
    "            if node.val == val:\n",
    "                return node.next\n",
    "            else:\n",
    "                node.next=func(node.next,val)\n",
    "                return node\n",
    "        return func(head,val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        cur = head\n",
    "        prev = None\n",
    "        while cur and cur.val != val:\n",
    "            prev = cur\n",
    "            cur = cur.next\n",
    "        if prev is None:\n",
    "            head = cur.next\n",
    "        elif cur:\n",
    "            prev.next = cur.next\n",
    "        \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "        head.next = self.deleteNode(head.next,val)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        # if head.val == val:\n",
    "        #     return head.next\n",
    "        # pre = head\n",
    "        # cur = head.next\n",
    "        # while cur:\n",
    "        #     if cur.val == val:\n",
    "        #         pre.next = cur.next\n",
    "        #     else:\n",
    "        #         pre = cur\n",
    "        #     cur = cur.next\n",
    "        # return head\n",
    "\n",
    "        #   递归\n",
    "        if head is None:\n",
    "            return None\n",
    "        \n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "        else:\n",
    "            head.next = self.deleteNode(head.next,val)\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "        pre = head\n",
    "        cur = head.next\n",
    "        while not cur.val == val and cur:\n",
    "            pre = cur\n",
    "            cur = cur.next\n",
    "        pre.next = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val: return head.next # 要删去的节点在开头\n",
    "        pre, cur = head, head.next\n",
    "        while cur and cur.val != val: # 遍历链表或者找到要删除的节点\n",
    "            pre, cur = pre.next, cur.next\n",
    "        pre.next = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        dum = ListNode(0)\n",
    "        dum.next = head\n",
    "        cur = dum\n",
    "        while head:\n",
    "            if head.val == val:\n",
    "                cur.next = head.next\n",
    "                return dum.next\n",
    "            head = head.next\n",
    "            cur = cur.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val: return head.next\n",
    "        pre, cur = head, head.next\n",
    "        while cur and cur.val != val:\n",
    "            pre, cur = cur, cur.next\n",
    "        if cur: pre.next = cur.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        # 删除的是头节点\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "\n",
    "        pre, cur = head, head.next\n",
    "        while cur:\n",
    "            if cur.val == val:\n",
    "                pre.next = cur.next\n",
    "                break\n",
    "            pre, cur = cur, cur.next\n",
    "            \n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:\n",
    "            head = head.next\n",
    "\n",
    "        pre, cur = head, head.next\n",
    "        while cur:\n",
    "            if cur.val==val:\n",
    "                pre.next = cur.next\n",
    "                break\n",
    "            else:\n",
    "                pre,cur = cur, cur.next\n",
    "        return head            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "\n",
    "        def drop(pre,cur):\n",
    "            if cur.val == val:\n",
    "                pre.next = cur.next\n",
    "            else:\n",
    "                drop(cur, cur.next)\n",
    "\n",
    "        drop(head, head.next)\n",
    "\n",
    "        return head\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "        \n",
    "        pre, cur = head, head.next\n",
    "        while cur:\n",
    "            if cur.val == val:\n",
    "                pre.next = cur.next\n",
    "                break\n",
    "            else:\n",
    "                cur = cur.next\n",
    "                pre = pre.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val: return head.next\n",
    "        pre, cur = head, head.next\n",
    "        while cur and cur.val != val:\n",
    "            pre, cur = cur, cur.next\n",
    "        if cur: pre.next = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if not head:\n",
    "            return head \n",
    "            \n",
    "        if head.val == val:\n",
    "            return head.next \n",
    "\n",
    "        head.next = self.deleteNode(head.next, val)\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:return head.next\n",
    "        cur, pre = head.next, head\n",
    "        while cur and cur.val != val:\n",
    "            pre, cur =  cur, cur.next\n",
    "        if cur:\n",
    "            pre.next = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val: return head.next\n",
    "        pre, cur = head, head.next\n",
    "        while cur and cur.val != val:\n",
    "            pre, cur = cur, cur.next\n",
    "        if cur: pre.next = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "        head.next = self.deleteNode(head.next, val)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        dummy = ListNode(0, head)\n",
    "        p = dummy\n",
    "        while p.next:\n",
    "            if p.next.val == val:\n",
    "                break\n",
    "            p = p.next\n",
    "        p.next = p.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val==val:\n",
    "            return head.next\n",
    "        temp=head\n",
    "        while(head.next!=None):\n",
    "            if head.next.val==val:\n",
    "                head.next=head.next.next\n",
    "                break\n",
    "            else:\n",
    "                head=head.next\n",
    "        return temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        dummy = ListNode(val = None, next = head)\n",
    "        current = dummy \n",
    "        while current.next:\n",
    "            if current.next.val == val:\n",
    "                current.next = current.next.next\n",
    "                break  \n",
    "            current = current.next \n",
    "        return dummy.next \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        n1= head\n",
    "        while n1.next != None:\n",
    "            if n1.val ==val:\n",
    "                head = n1.next\n",
    "            if n1.next.val == val:\n",
    "               n1.next = n1.next.next\n",
    "               break\n",
    "            else:\n",
    "                n1 = n1.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head == None:\n",
    "            return head\n",
    "        dummy_head = ListNode(val=-1, next=head)\n",
    "        ptr = dummy_head\n",
    "        while ptr.next != None:\n",
    "            if ptr.next.val == val:\n",
    "                ptr.next = ptr.next.next\n",
    "            else:\n",
    "                ptr = ptr.next\n",
    "        return dummy_head.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        start = head\n",
    "        if start.val == val:\n",
    "            head = head.next\n",
    "        while start and start.next:\n",
    "            if start.next.val == val:\n",
    "                start.next = start.next.next\n",
    "                return head\n",
    "            start = start.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val==val:\n",
    "            return head.next\n",
    "        temp=head\n",
    "        while(head.next!=None):\n",
    "            if head.next.val==val:\n",
    "                head.next=head.next.next\n",
    "                break\n",
    "            else:\n",
    "                head=head.next\n",
    "            \n",
    "        return temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "\n",
    "        pre,cur =  head,head.next\n",
    "\n",
    "        while cur and cur.val != val :\n",
    "            pre,cur =  cur,cur.next\n",
    "        \n",
    "        if cur:\n",
    "            pre.next = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        cur = head\n",
    "        dum = pre = ListNode(0)\n",
    "        pre.next = head\n",
    "        while cur:\n",
    "            if cur.val == val:\n",
    "                pre.next = cur.next\n",
    "                break\n",
    "            pre = cur\n",
    "            cur = cur.next\n",
    "        return dum.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "\n",
    "        if head.val == val: \n",
    "            return head.next\n",
    "        pre, cur = head, head.next\n",
    "        while cur and cur.val != val:\n",
    "            pre, cur = cur, cur.next\n",
    "        if cur: \n",
    "            pre.next = cur.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val==val:\n",
    "            return head.next\n",
    "        pre,cur=head,head.next\n",
    "        while cur and cur.val != val:\n",
    "            pre,cur=cur,cur.next\n",
    "        if cur:\n",
    "                pre.next=cur.next\n",
    "        return head\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:\n",
    "            head = head.next\n",
    "\n",
    "        pre = head\n",
    "        cur = head.next\n",
    "        while cur and cur.val != val:\n",
    "            pre = cur\n",
    "            cur = cur.next\n",
    "        if cur:\n",
    "            pre.next = cur.next\n",
    "        return head "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val: return head.next\n",
    "        pre, cur = head, head.next\n",
    "        while cur and cur.val != val:\n",
    "            pre, cur = cur, cur.next\n",
    "        if cur: pre.next = cur.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "        a = head\n",
    "        while (head.next != None):\n",
    "            if head.next.val == val:\n",
    "                head.next = head.next.next\n",
    "                break\n",
    "            else:\n",
    "                head = head.next\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "        now = head\n",
    "        while now.next:\n",
    "            if now.next.val == val:\n",
    "                now.next = now.next.next\n",
    "                return head\n",
    "            else:\n",
    "                now = now.next\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "        new_head = head\n",
    "        while tmp:=new_head.next:\n",
    "                if tmp.val == val:\n",
    "                    new_head.next = tmp.next\n",
    "                    return head\n",
    "                new_head = new_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val :\n",
    "            return head.next\n",
    "        pre = head \n",
    "        cur = head.next\n",
    "        while cur!=None and cur.val != val :\n",
    "            pre = cur \n",
    "            cur = cur.next\n",
    "        if cur!=None: \n",
    "            pre.next = cur.next \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:\n",
    "            head = head.next\n",
    "            return head\n",
    "        pre = head\n",
    "        cur = head.next\n",
    "        while cur:\n",
    "            if cur.val == val:\n",
    "                pre.next = cur.next\n",
    "                break\n",
    "            pre = pre.next\n",
    "            cur = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "        a = head\n",
    "        while (head.next != None):\n",
    "            if head.next.val == val:\n",
    "                head.next = head.next.next\n",
    "                break\n",
    "            else:\n",
    "                head = head.next\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val==val:\n",
    "            head=head.next\n",
    "            return head\n",
    "        ret=head\n",
    "        while head:\n",
    "            if head.next.val==val:\n",
    "                head.next=head.next.next\n",
    "                break\n",
    "            else:\n",
    "                head=head.next\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val: return head.next\n",
    "\n",
    "        pre,cur = head, head.next\n",
    "        while cur and cur.val !=val:\n",
    "            pre, cur = cur, cur.next\n",
    "        if cur:\n",
    "            pre.next = cur.next\n",
    "        \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head is None:\n",
    "            return head\n",
    "        else:\n",
    "            cur = dummy = ListNode(0, head)\n",
    "            while cur.next is not None:\n",
    "                if cur.next.val == val:\n",
    "                    cur.next = cur.next.next\n",
    "                    return dummy.next\n",
    "                else:\n",
    "                    cur = cur.next\n",
    "            return dummy.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head is None:\n",
    "            return None\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "        cur = head\n",
    "        while cur.next:\n",
    "            if cur.next.val == val:\n",
    "                cur.next = cur.next.next\n",
    "                break\n",
    "            cur = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "        c, p = head, head.next\n",
    "        while p.val != val and p:\n",
    "            c = p\n",
    "            p = p.next\n",
    "        if p:\n",
    "            c.next = p.next\n",
    "            return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        dummyhead=ListNode(0,head)\n",
    "        cur=dummyhead\n",
    "        while cur and cur.next:\n",
    "            if cur.next.val==val:\n",
    "                cur.next=cur.next.next\n",
    "            cur=cur.next\n",
    "        return dummyhead.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        node = head\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "        while node.next.val != val:\n",
    "            node = node.next\n",
    "\n",
    "        node.next = node.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        ## 双指针\n",
    "        # if head.val == val:\n",
    "        #     return head.next\n",
    "        # pre = head\n",
    "        # node = head.next\n",
    "        # while node:\n",
    "        #     if node.val == val:\n",
    "        #         pre.next = node.next\n",
    "        #         node.next = None\n",
    "        #         break\n",
    "        #     pre = node\n",
    "        #     node = node.next\n",
    "        # return head\n",
    "\n",
    "        ## 单指针思路\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "        temp = head\n",
    "        while head.next:\n",
    "            if head.next.val == val:\n",
    "                head.next = head.next.next\n",
    "                break\n",
    "            head = head.next\n",
    "        \n",
    "        return temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.val == val:\n",
    "                return cur.next\n",
    "            if cur.next != None and cur.next.val == val:\n",
    "                cur.next = cur.next.next\n",
    "            cur = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val: return head.next\n",
    "        cnt = head\n",
    "        while cnt.next:\n",
    "            if cnt.next.val == val:\n",
    "                cnt.next = cnt.next.next\n",
    "            else:\n",
    "                cnt = cnt.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        cur, pre = head, head\n",
    "        if head.val == val : return head.next\n",
    "        while cur:\n",
    "            if cur.val == val:\n",
    "                pre.next = cur.next\n",
    "                break\n",
    "            else:\n",
    "\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        dumy = ListNode(next=head)\n",
    "        pre = dumy\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.val == val:\n",
    "                pre.next = cur.next\n",
    "                break\n",
    "            else:\n",
    "                cur = cur.next\n",
    "                pre = pre.next\n",
    "        return dumy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val==val: return head.next\n",
    "        pre,cur=head,head.next\n",
    "        while cur:\n",
    "            if cur.val==val:\n",
    "                pre.next=cur.next\n",
    "                break\n",
    "            else:\n",
    "                pre=cur\n",
    "                cur=cur.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val :\n",
    "            return head.next\n",
    "        pre = head \n",
    "        cur = head.next\n",
    "        while cur!=None and cur.val != val :\n",
    "            pre = cur \n",
    "            cur = cur.next\n",
    "        if cur!=None: \n",
    "            pre.next = cur.next \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        \n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.val != val:\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "            else:\n",
    "                if pre:\n",
    "                    pre.next = cur.next\n",
    "                else:\n",
    "                    pre = cur.next\n",
    "                    head = pre\n",
    "\n",
    "                break\n",
    "\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "        pre, cur = head, head.next\n",
    "        while cur and cur.val != val:\n",
    "            pre, cur = cur, cur.next\n",
    "        if cur:\n",
    "            pre.next = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        new_head = ListNode(0)\n",
    "        new_head.next = head\n",
    "        cur = new_head\n",
    "        while cur and cur.next:\n",
    "            if cur.next.val == val:\n",
    "                cur.next = cur.next.next\n",
    "            else:\n",
    "                cur = cur.next\n",
    "        return new_head.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        pre = dummy\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.val == val:\n",
    "                pre.next = cur.next\n",
    "                cur = cur.next\n",
    "            else:\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "        pre = head \n",
    "        cur = head.next \n",
    "        while cur:\n",
    "            if cur.val == val:\n",
    "                pre.next = cur.next\n",
    "            pre = pre.next\n",
    "            cur = cur.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val :\n",
    "            return head.next\n",
    "        pre = head \n",
    "        cur = head.next\n",
    "        while cur and cur.val != val :\n",
    "            pre = cur \n",
    "            cur = cur.next\n",
    "        if cur: \n",
    "            pre.next = cur.next \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        n1, n2 = None, head\n",
    "        while n2:\n",
    "            \n",
    "            if n2.val == val:\n",
    "                if n2.next:\n",
    "                    if not n1:\n",
    "                        return n2.next\n",
    "                    n1.next=n2.next\n",
    "                else:\n",
    "                    n1.next = None\n",
    "                break\n",
    "            else:\n",
    "                n1 = n2\n",
    "                n2 = n2.next\n",
    "        return head\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        # if head.val ==val:\n",
    "        #     return head.next\n",
    "        # pre,cur=head,head.next\n",
    "\n",
    "        # while cur and cur.val!=val:\n",
    "            \n",
    "        #     pre,cur=cur ,cur.next\n",
    "        \n",
    "        # pre.next=cur.next\n",
    "        # return head\n",
    "# 执行用时：52 ms, 在所有 Python3 提交中击败了37.18%的用户\n",
    "# 内存消耗：16.5 MB, 在所有 Python3 提交中击败了39.81%的用户\n",
    "        if head.val==val:\n",
    "            return head.next\n",
    "        \n",
    "        origin=head\n",
    "        while head.next !=None:\n",
    "            if head.next.val==val:\n",
    "                head.next=head.next.next\n",
    "                break\n",
    "            else:\n",
    "                head=head.next\n",
    "        \n",
    "        return origin\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head is None:\n",
    "            return None\n",
    "        dummy_node = ListNode(-1)\n",
    "        dummy_node.next = head\n",
    "        pre, cur = dummy_node, head\n",
    "        while cur:\n",
    "            if cur.val == val:\n",
    "                pre.next = cur.next\n",
    "                break\n",
    "            pre = cur\n",
    "            cur = cur.next\n",
    "        return dummy_node.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "        c, p = head, head.next\n",
    "        while p.val != val and p:\n",
    "            c = p\n",
    "            p = p.next\n",
    "        if p:\n",
    "            c.next = p.next\n",
    "            return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val: return head.next\n",
    "        cnt = head\n",
    "        while cnt.next:\n",
    "            if cnt.next.val == val:\n",
    "                cnt.next = cnt.next.next\n",
    "            else:\n",
    "                cnt = cnt.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.val == val:\n",
    "                return cur.next\n",
    "            if cur.next!=None and cur.next.val == val:\n",
    "                cur.next = cur.next.next\n",
    "            cur = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:return head.next\n",
    "        pre,cur = head,head.next\n",
    "        while cur and cur.val!=val:\n",
    "            pre,cur = cur,cur.next\n",
    "        if cur:pre.next=cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val: return head.next\n",
    "        pre, cur = head, head.next\n",
    "        while cur and cur.val != val:\n",
    "            pre, cur = cur, cur.next\n",
    "        if cur: pre.next = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        head_0 = head\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "        while(head.next != None):\n",
    "            next_node = head.next\n",
    "            if next_node.val == val:\n",
    "                head.next=next_node.next\n",
    "                return head_0\n",
    "            head = head.next\n",
    "        return head_0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "        prefix = head\n",
    "        cursor = head.next\n",
    "\n",
    "\n",
    "        while cursor:\n",
    "            if cursor.val == val:\n",
    "                prefix.next = cursor.next\n",
    "                return head\n",
    "            prefix = cursor\n",
    "            cursor = cursor.next\n",
    "\n",
    "        return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:  \n",
    "            return head.next\n",
    "        head_0 = head\n",
    "        while(head.next != None):\n",
    "            if head.next.val == val:\n",
    "                head.next=head.next.next\n",
    "                break\n",
    "            head = head.next\n",
    "        return head_0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "        c, p = head, head.next\n",
    "        while p.val != val and p:\n",
    "            c = p\n",
    "            p = p.next\n",
    "        if p:\n",
    "            c.next = p.next\n",
    "            return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:return head.next\n",
    "        pre = head\n",
    "        while pre.next and pre.next.val!=val:\n",
    "            pre = pre.next\n",
    "        if pre.next:pre.next=pre.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if val == head.val:\n",
    "            head=head.next\n",
    "            return head\n",
    "        pre , cur = head, head.next\n",
    "        while cur and cur.val != val:\n",
    "            pre = cur \n",
    "            cur = cur.next\n",
    "        if cur:\n",
    "            pre.next = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        pnode = ListNode(-1)\n",
    "        pnode.next = head\n",
    "        res = pnode\n",
    "\n",
    "        while pnode.next != None:\n",
    "            if pnode.next.val == val:\n",
    "                pnode.next = pnode.next.next\n",
    "                break\n",
    "            pnode = pnode.next\n",
    "\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:  \n",
    "            return head.next\n",
    "        head_0 = head\n",
    "        while(head.next != None):\n",
    "            if head.next.val == val:\n",
    "                head.next=head.next.next\n",
    "                break\n",
    "            head = head.next\n",
    "        return head_0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:\n",
    "            return head.next\n",
    "        pre = head \n",
    "        cur = head.next \n",
    "        while cur:\n",
    "            if cur.val == val:\n",
    "                pre.next = cur.next\n",
    "            pre = pre.next\n",
    "            cur = cur.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val: return head.next\n",
    "        pre, cur = head, head.next\n",
    "        while cur and cur.val != val:\n",
    "            pre, cur = cur, cur.next\n",
    "        if cur: pre.next = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val:return head.next\n",
    "        pre = head\n",
    "        while pre.next and pre.next.val!=val:\n",
    "            pre = pre.next\n",
    "        if pre.next:pre.next=pre.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        head_0 = head\n",
    "        if head.val == val:  \n",
    "            return head.next\n",
    "        while(head.next != None):\n",
    "            if head.next.val == val:\n",
    "                head.next=head.next.next\n",
    "                return head_0\n",
    "            head = head.next\n",
    "        return head_0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val == val: return head.next\n",
    "        pre, cur = head, head.next\n",
    "        while cur and cur.val != val:\n",
    "            pre, cur = cur, cur.next\n",
    "        if cur: pre.next = cur.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head.val==val: return head.next\n",
    "        p,c=head,head.next\n",
    "        while c and c.val!=val:\n",
    "            p,c = c, c.next\n",
    "        if c: p.next=c.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def deleteNode(self, head: ListNode, val: int) -> ListNode:\n",
    "        dummy=ListNode(next=head)\n",
    "        cur=dummy\n",
    "        while cur.next:\n",
    "            if cur.next.val==val:\n",
    "                cur.next=cur.next.next\n",
    "            else:\n",
    "                cur=cur.next\n",
    "        return dummy.next\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
